package com.fanshuai.bitmap.bitmap;

import java.util.ArrayList;
import java.util.List;

public class BitMap implements IBitMap {
    private int[] arr;

    public BitMap(int maxValue) {
        arr = new int[maxValue];
    }

    @Override
    public void insert(int value) {
        if (value < 0) {
            value = -value;
        }

        int index = value >> 5;
        int bitIndex = value & 31;

        arr[index] |= (1 << bitIndex);
    }

    @Override
    public void delete(int value) {
        if (value < 0) {
            value = -value;
        }

        int index = value >> 5;
        int bitIndex = value & 31;

        arr[index] &= ~(1 << bitIndex);
    }

    @Override
    public boolean exists(int value) {
        if (value < 0) {
            value = -value;
        }

        int index = value >> 5;
        int bitIndex = value & 31;

        return (arr[index] & (1 << bitIndex)) > 0;
    }

    @Override
    public List<Integer> getAll() {
        List<Integer> list = new ArrayList<>();
        for (int index = 0; index < arr.length; index++) {
            int base = index << 5;
            for (int bitIndex = 0; bitIndex < 32; bitIndex++) {
                if ((arr[index] & (1 << bitIndex)) > 0) {
                    list.add(base + bitIndex);
                }
            }
        }

        return list;
    }

    /**
     * 去重并排序
     * @param list
     * @return
     */
    public static List<Integer> uniqueAndSort(List<Integer> list, int maxValue) {
        BitMap bitMap = new BitMap(maxValue);
        for (Integer i : list) {
            bitMap.insert(i);
        }

        return bitMap.getAll();
    }
}
